//
// Created by TNJ on 2021/6/25.
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "radix_sort.h"

//求取最大值
static int get_max(int *arr, int length){
    int i = 0;
    int max = 0;

    max = arr[0];
    for(i = 1; i < length; i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }
    return max;
}

//计数排序
void count_sort(int *arr, int length, int exp){
    if(arr == NULL || length <= 0 || exp <= 0){
        return;
    }

    int bucket[10] = {0};
    int *output = (int *)malloc(sizeof(int) * length);
    if(output == NULL){
        return;
    }
    memset(output, 0, sizeof(int) * length);
    int i = 0;
    for(i = 0; i < length; i++){
        bucket[(arr[i] / exp) % 10]++;
    }
    for(i = 1; i < length; i++){
        bucket[i] += bucket[i - 1];
    }
    for(i = length - 1; i >= 0; i--){
        output[bucket[(arr[i] / exp) % 10] - 1] = arr[i];
        bucket[(arr[i] / exp) % 10]--;
    }
    for(i = 0; i < length; i++){
        arr[i] = output[i];
    }
    free(output);
}

//基数排序
void radix_sort(int *arr, int length){
    if(arr == NULL || length <= 0){
        return;
    }

    int exp = 0;
    int max = get_max(arr, length);
    for(exp = 1; max / exp; exp *= 10){
        count_sort(arr, length, exp);
    }
}
